package com.zjj.lbw.algorithm.sort;

import java.util.Arrays;

/**
 * @author zhanglei.zjj
 * @description 希尔排序
 * @date 2023/3/25 18:11
 */
public class ShellSort {
    public static void main(String[] args) {
        int[] unsortedArr = new int[]{4, 2, 28, 33, 12, 1};
        shellSort(unsortedArr);
    }

    static void shellSort(int[] arr) {
        System.out.println("排序前元素顺序：" + arr);
        // 增量
        int gap = arr.length / 2;
        while (gap > 0) {
            for (int i = gap; i < arr.length; i++) {
                // 已排序的元素下标
                int sortedIndex = i - gap;

                // 待排序元素
                int tobeSortedVal = arr[sortedIndex + gap];

                int insetIndex = sortedIndex;
                while (insetIndex >= 0 && arr[insetIndex] > tobeSortedVal) {
                    // 元素右移gap位
                    arr[insetIndex + gap] = arr[insetIndex];
                    insetIndex -= gap;
                }
                arr[insetIndex + gap] = tobeSortedVal;
            }
            gap /= 2;
        }
        System.out.println("升序排序后的元素顺序：" + Arrays.toString(arr));
    }
}
